package pri.zjy.hash;

import java.util.*;

/**
 * @author zhangjy
 * @description 三数之和
 * @date 2025/6/2 22:39
 */
public class ThreeSum_15 {

    public static void main(String[] args) {
        ThreeSum_15 threeSum15 = new ThreeSum_15();

        int[] nums = {1, -1, -1, 0};
//        int[] nums = {-1, 0, 1, 2, -1, -4};
//        int[] nums = {0, 0, 0, 0};
//        threeSum15.threeSum(nums).forEach(System.out::println);
        threeSum15.threeSum2(nums).forEach(System.out::println);
    }

    /**
     * 参考dmsxl：双指针
     */
    public List<List<Integer>> threeSum2(int[] nums) {
        if (nums.length == 0) return null;

        // 1.升序排列
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        // 2.获取不重复的三元组 a+b+c=0
        for (int i = 0; i < nums.length; i++) {
            // 升序后，第一个元素>0，后续三元组肯定不满足条件
            if (nums[i] > 0) return ans;

            // 2.1.找a
            int a = nums[i];
            // a去重
            // 与前一个元素相比，因为nums有序，前一个元素已经找过三元组，而当前i还没有
            if (i > 0 && a == nums[i - 1]) continue;

            // 2.2.找b、c
            int left = i + 1, right = nums.length - 1;
            // 同一个a可能找到多个三元组（需要去重）
            while (left < right) {
                int sum = a + nums[left] + nums[right];
                if (sum > 0) {
                    // sum偏大，right左移（因为nums升序）
                    right--;
                } else if (sum < 0) {
                    // sum偏大，left右移
                    left++;
                } else {
                    // 找到三元组，并记录
//                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重b
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    // 去重c
                    while (left < right && nums[right] == nums[right - 1]) right--;

                    // 先记录三元组，再去重；先去重、再记录三元组，这两种方式都可以。
                    // 因为去重后指向的下标，仍然属于当前三元组，只是不是重复三元组中的第一个
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重后，再移动left、right（因为当前三元组记录后，本就要移动指针）
                    left++;
                    right--;
                }
            }
        }

        return ans;
    }

    /**
     * 错误解法：没有去重
     * <p>
     * 思路：题目要求，找到所有互不相等、不重复的三元组（输出的顺序和三元组的顺序并不重要），要求三元组的三者之和为0
     */
    public List<List<Integer>> threeSum(int[] nums) {
        if (nums.length == 0) return null;

        // 1.升序排列
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();

        // 2.找不重复的三元组（顺序不重要）
        // a+b+c=0，分别找a、b、c
        for (int i = 0; i < nums.length; i++) {
            // 升序排列后，如果当前元素>0，那么后续不可能组成等于0的三元组
            if (nums[i] > 0) return ans;

            int a = nums[i];
            // 分别找b、c
            int left = i + 1;
            int right = nums.length - 1;
            // 为什么不是left <= right？——因为当left==right，那么指向同一个下标，加上nums[i]一共只有两个数，但是题目要求找三元组，不符合题意；所以只能是left < right。
            while (left < right) {
                int sum = a + nums[left] + nums[right];
                if (sum > 0) {
                    // 若 a+b+c>0，表明b偏小，要将b右移，直到a+b+c=0（因为nums已经升序排列）
                    left++;
                } else if (sum < 0) {
                    // 若 a+b+c<0，c偏大，左移直到a+b+c=0
                    right--;
                } else {
                    // 找到三者之和等于0的三元组
                    right--;
                    left++;
                    // 1.与前一位相等，则找到的是重复三元组
                    if (i > 0 && nums[i] == nums[i - 1]) continue;

                    // 2.记录不重复三元组
                    ans.add(Arrays.asList(a, nums[left], nums[right]));
                }
            }

        }

        return ans;
    }

}
